|
Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. The boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT) and answer set programming (ASP) can be roughly thought of as certain forms of the constraint satisfaction problem. Examples of simple problems that can be modeled as a constraint satisfaction problem * Eight queens puzzle * Map coloring problem * Sudoku, Futoshiki, Kakuro (Cross Sums), Numbrix, Hidato and many other logic puzzles. Examples demonstrating the above are often provided with tutorials of ASP, boolean SAT and SMT solvers. In the general case, constraint problems can be much harder, and may not be expressible in some of these simpler systems. "Real life" examples include automated planning〔(Dynamic Flexible Constraint Satisfaction and Its Application to AI Planning ), Ian Miguel - slides.〕 and resource allocation. ==Formal definition== Formally, a constraint satisfaction problem is defined as a triple , where : is a set of variables, : is a set of the respective domains of values, and : is a set of constraints. Each variable can take on the values in the nonempty domain . Every constraint is in turn a pair , where is a subset of variables and is an -ary relation on the corresponding subset of domains . An ''evaluation'' of the variables is a function from a subset of variables to a particular set of values in the corresponding subset of domains. An evaluation satisfies a constraint if the values assigned to the variables satisfies the relation . An evaluation is ''consistent'' if it does not violate any of the constraints. An evaluation is ''complete'' if it includes all variables. An evaluation is a ''solution'' if it is consistent and complete; such an evaluation is said to ''solve'' the constraint satisfaction problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「constraint satisfaction problem」の詳細全文を読む スポンサード リンク
|